#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include "LinkList.h"

// 非循环单向链表

typedef struct Node
{
    int data;           // 数据域
    struct Node *pNext; // 指针域
} NODE, *PNODE;         // NODE等价于struct Node, PNODE等价于struct Node*

// 函数声明

PNODE easy_create_list(void);                      // 简单版创建链表
PNODE create_list(void);                           // 创建节点
void traverse_list(PNODE pHead);                   // 遍历链表
bool is_empty(const PNODE pHead);                  // 判断链表是否为空
int length_list(const PNODE pHead);                // 求链表长度
void insert_list(PNODE pHead, int pos, int val);   // 在第pos个元素前面插入一个节点，使之成为第pos个节点，其存储的数据为val
bool delete_list(PNODE pHead, int pos, int *pVal); // 删除链表节点
void sort_list(PNODE pHead);                       // 链表排序
void inversion_list(PNODE pHead);                  // 链表倒序

int main()
{
    PNODE pHead = NULL;
    int val = 0;

    pHead = create_list();
    if (pHead == NULL)
    {
        printf("链表开辟失败");
        return 1;
    }
    // traverse_list(pHead);

    // if(is_empty(pHead))
    //     printf("链表为空\n");
    // else
    //     printf("链表不为空\n");

    // printf("链表长度为 %d\n", length_list(pHead));

    // sort_list(pHead);

    // insert_list(pHead, 4, 10);

    // if (delete_list(pHead, 4, &val))
    // {
    //     printf("删除的数据的值为 %d\n", val);
    // }

    inversion_list(pHead);

    traverse_list(pHead);

    return 0;
}

PNODE create_list() // 可以创建空链表
{
    int len = -1; // 存放有效节点个数
    int val = 0;  // 临时存放节点中用户输入的数据内容
    printf("输入你想创建链表的节点个数: ");
    fflush(stdout);
    while (len < 0)
    {
        scanf("%d", &len);
        if (len < 0)
        {
            printf("输入错误，请重新输入:");
            fflush(stdout);
        }
    }
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (pHead == NULL)
    {
        printf("分配失败，程序终止！\n");
        exit(-1);
    }
    PNODE pNew = pHead; // 临时节点
    int i = 0;
    for (i = 0; i < len; i++)
    {
        printf("请输入第%d个节点数据的内容:", i + 1);
        fflush(stdout);
        scanf("%d", &val);
        pNew->pNext = (PNODE)malloc(sizeof(NODE));
        pNew = pNew->pNext;
        if (pNew == NULL)
        {
            printf("分配失败，程序终止！\n");
            exit(-1);
        }
        pNew->data = val;
    }
    pNew->pNext = NULL;
    printf("\n\n");
    return pHead;
}

void traverse_list(PNODE pHead)
{
    PNODE pTemp = pHead->pNext;
    int i = 0;
    while (pTemp != NULL)
    {
        i++;
        printf("第%d个节点数据为 %d \n", i, pTemp->data);
        pTemp = pTemp->pNext;
    }
    printf("链表遍历完毕！\n");
    return;
}

PNODE easy_create_list()
{
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    PNODE pNew = pHead;
    int i = 0;
    for (i = 0; i < 10; i++)
    {
        pNew->pNext = (PNODE)malloc(sizeof(NODE));
        pNew = pNew->pNext;
        pNew->data = i;
    }
    pNew->pNext = NULL;
    return pHead;
}

bool is_empty(const PNODE pHead)
{
    if (pHead->pNext == NULL)
        return true;
    else
        return false;
}

int length_list(const PNODE pHead)
{
    PNODE pTemp = pHead->pNext;
    int len = 0;
    while (pTemp != NULL)
    {
        len++;
        pTemp = pTemp->pNext;
    }
    return len;
}

void insert_list(PNODE pHead, int pos, int val) // pos从1开始。在第pos个元素前面插入一个节点，使之成为第pos个节点，其存储的数据为val
{
    if (pos < 1 || pos > length_list(pHead) + 2)
    {
        printf("链表插入节点失败,pos值非法!(pos应从1开始,且不大于节点个数+1)\n");
        return;
    }
    int i = 0;
    PNODE pTemp = pHead;
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if (NULL == pNew)
    {
        printf("动态内存分配失败!\n");
        exit(-1);
    }
    for (i = 0; i < pos - 1; i++)
    {
        pTemp = pTemp->pNext;
    }
    pNew->data = val;
    pNew->pNext = pTemp->pNext;
    pTemp->pNext = pNew;
    return;
}

bool delete_list(PNODE pHead, int pos, int *pVal)
{
    if (pos < 1 || pos > length_list(pHead))
    {
        printf("链表删除节点失败,pos值非法!(pos应从1开始,且不大于节点个数)\n");
        return false;
    }
    int i = 0;
    PNODE pTemp = pHead;
    for (i = 0; i < pos - 1; i++)
    {
        pTemp = pTemp->pNext;
    }
    *pVal = (pTemp->pNext)->data;
    pTemp->pNext = (pTemp->pNext)->pNext;
    return true;
}

void sort_list(PNODE pHead)
{
    PNODE Pi = NULL;
    PNODE Pj = NULL;
    for (Pi = pHead->pNext; Pi->pNext != NULL; Pi = Pi->pNext)
    {
        for (Pj = Pi->pNext; Pj != NULL; Pj = Pj->pNext)
        {
            if (Pi->data > Pj->data)
            {
                int temp = Pi->data;
                Pi->data = Pj->data;
                Pj->data = temp;
            }
        }
    }
    return;
}

void inversion_list(PNODE pHead) // 链表倒序
{
    assert(pHead->pNext != NULL);
    PNODE Next = NULL;
    PNODE Prev = NULL;
    for (Next = pHead->pNext->pNext, Prev = pHead->pNext; Next != NULL;)
    {
        PNODE t = Prev;
        Prev = Next;
        Next = Next->pNext;
        Prev->pNext = t;
    }
    pHead->pNext->pNext = NULL;
    pHead->pNext = Prev;
    printf("链表倒序完成!\n");
    return;
}

//